/*
https://leetcode.cn/problems/count-different-palindromic-subsequences/description/
730. 统计不同回文子序列
方钊堉 2024.10.19
区间dp
*/
class Solution 
{
public:
    int countPalindromicSubsequences(string text) 
    {
        const int MOD = (int)(1e9 + 7); // 定义模数
        int length = (int)text.size(); // 字符串长度

        // 动态规划数组 dp[charID][start][end] 表示从 start 到 end 区间内以第 charID ('a'-'d') 开头和结尾的回文子序列个数
        int dp[4][length][length];
        memset(dp, 0, sizeof(dp)); // 初始化动态规划数组为0

        // 初始化单字符回文子序列计数
        for (int i = 0; i < length; i++) 
        {
            int charID = (int)(text[i] - 'a'); // 计算字符在 'a'-'d' 中的位置
            dp[charID][i][i] = 1; // 单个字符自身形成一个回文子序列
        }

        // 枚举所有可能的子串长度，从短到长
        for (int subLength = 2; subLength <= length; subLength++) 
        {
            // 枚举所有可能的起始位置
            for (int start = 0; start < length - subLength + 1; start++) 
            {
                int end = start + subLength - 1; // 根据起始位置和子串长度计算结束位置
                // 对于每个字符 'a'-'d'
                for (char c = 'a'; c <= 'd'; c++) 
                {
                    int charID = (int)(c - 'a'); // 计算字符在 'a'-'d' 中的位置
                    char leftChar = text[start], rightChar = text[end]; // 当前子串的首尾字符

                    // 如果首尾字符都等于当前考虑的字符
                    if (leftChar == c && rightChar == c) 
                    {
                        // 在内部子串的基础上增加所有可能的回文子序列，并加上 "cc" 和 "c" 这两种情况
                        for (int k = 0; k < 4; k++) 
                        {
                            dp[charID][start][end] += dp[k][start + 1][end - 1];
                            dp[charID][start][end] %= MOD;
                        }
                        dp[charID][start][end] += 2;
                        dp[charID][start][end] %= MOD;
                    } 
                    // 如果只有左端字符等于当前考虑的字符
                    else if (leftChar == c && rightChar != c) 
                    {
                        dp[charID][start][end] = dp[charID][start][end - 1];
                    } 
                    // 如果只有右端字符等于当前考虑的字符
                    else if (leftChar != c && rightChar == c) 
                    {
                        dp[charID][start][end] = dp[charID][start + 1][end];
                    } 
                    // 如果首尾字符都不等于当前考虑的字符
                    else 
                    {
                        dp[charID][start][end] = dp[charID][start + 1][end - 1];
                    }
                }
            }
        }

        // 计算最终结果
        int result = 0;
        for (int charID = 0; charID < 4; charID++) 
        {
            result += dp[charID][0][length - 1];
            result %= MOD;
        }
        return result;
    }
};